/**
 * 
 */
package string.passed2;

/**
 * Given a string, find the longest substring that contains at most 2 distinct characters.
 *
 *For example,
 *
 *Given s = �ababcbcbaaabbdef�,
 *
 *Below are two possible substrings that contains at most 2 distinct characters:
 *
 *  "baaabb" (6)
 *  "bcbcb" (5)
 *
 *The answer is "baaabb" since it is longer.
 * 
 * http://www.mitbbs.com/article_t1/JobHunting/32298851_0_1.html
 * 
 * @author xyyi
 * @since 01/27/2013
 * @version 01/27/2013
 * 
 */
public class LongestSubstringWithAtMostTwoDistinctCharacters {

	// Good interview
	public int lengthOfLongestSubstringTwoDistinct1(String s) {
		int start = 0, lastIndex = -1, maxLength = 0;
		for (int i = 1; i < s.length(); i++) {
			if (s.charAt(i) == s.charAt(i - 1)) continue;
			if (lastIndex > 0 && s.charAt(i) != s.charAt(lastIndex - 1)) {
				maxLength = Math.max(i - start, maxLength);
				start = lastIndex;
			}
			lastIndex = i;
		}
		
		return Math.max(maxLength, s.length() - start);
	}
	
	public String lengthOfLongestSubstringTwoDistinctStr1(String s) {
		int start = 0, lastIndex = -1, maxStart = 0, maxEnd = 0;
		for (int i = 1; i < s.length(); i++) {
			if (s.charAt(i) == s.charAt(i - 1)) continue;
			if (lastIndex > 0 && s.charAt(i) != s.charAt(lastIndex - 1)) {
				if (i - start > maxEnd - maxStart) {
					maxStart = start;
					maxEnd = i;
				}
				start = lastIndex;
			}
			lastIndex = i;
		}
		
		if (s.length() - start > maxEnd - maxStart) {
			maxStart = start;
			maxEnd = s.length();
		}
		
		return s.substring(maxStart, maxEnd);
	}
	
	// Best interview
	public int lengthOfLongestSubstringTwoDistinct2(String s) {
		int start = 0, numOfDistinct = 0, maxLength = 0;
		int[] counters = new int[256];
		for (int i = 0; i < s.length(); i++) {
			if (counters[s.charAt(i)] == 0)	numOfDistinct++;
			counters[s.charAt(i)]++;
			while (numOfDistinct > 2) {
				counters[s.charAt(start)]--;
				if (counters[s.charAt(start)] == 0) numOfDistinct--;
				start++;
			}
			maxLength = Math.max(i - start + 1, maxLength);
		}
		
		return maxLength;
	}
	
	public String find(String str) {
		if (str == null || str.isEmpty())
			return "";

		int start = 0, end = 0;
		int last1stI = 0, last2ndI = 0;
		int maxStart = 0, maxEnd = 0;

		// find 1st char index and 2nd char index
		for (int i = 1; i < str.length(); i++) {
			if (str.charAt(last1stI) == str.charAt(i)) {
				last1stI = i;
			} else {
				last2ndI = i;
				end = i;
				maxEnd = i;
				break;
			}
		}

		if (last2ndI == 0)
			return "";

		for (int i = last2ndI + 1; i < str.length(); i++) {
			char c = str.charAt(i);
			if (c != str.charAt(last1stI) && c != str.charAt(last2ndI)) {
				start = last1stI + 1;
				last1stI = last2ndI;
				// last2ndI = i;
				// end = i;
			}

			if (c == str.charAt(last1stI)) {
				last1stI = last2ndI;
				// last2ndI = i;
				// end = i;
			}

			if (c == str.charAt(last2ndI)) {
				// last2ndI = i;
				// end = i;
			}

			last2ndI = i;
			end = i;

			if (end - start > maxEnd - maxStart) {
				maxStart = start;
				maxEnd = end;
			}
		}

		return str.substring(maxStart, maxEnd + 1);
	}

	/**
	 * 
	 */
	public LongestSubstringWithAtMostTwoDistinctCharacters() {

	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		LongestSubstringWithAtMostTwoDistinctCharacters lscamtdc = new LongestSubstringWithAtMostTwoDistinctCharacters();
		String str = "ababcbcbaaabbdef";
		String expectation = "baaabb";
//		String str = "eceba";
//		String expectation = "ece";
		int size = lscamtdc.lengthOfLongestSubstringTwoDistinct2(str);
		System.out.printf("answer: %d, expected: %d\n", size, 6);
		String subStr = lscamtdc.lengthOfLongestSubstringTwoDistinctStr1(str);
		System.out.printf("answer: %s, expected: %s\n", subStr, expectation);
		
		String result = lscamtdc.find(str);
		System.out.printf("answer: %s, expected: %s\n", result, expectation);
	}

}
